package com.faxon.leetcode.l;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Faxon
 * @version 1.0
 * @date 2020-05-03 17:48
 * 119. 杨辉三角 II
 * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 * 示例:
 * 输入: 3
 * 输出: [1,3,3,1]
 **/
public class LeetCode119 {
    public static List<Integer> getRow(int rowIndex) {
        if (rowIndex < 0) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>(rowIndex + 1);
        List<Integer> cache = new ArrayList<>(rowIndex + 1);
        res.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            cache.add(1);
            for (int j = 1; j <= i; j++) {
                Integer num = j == i ? res.get(j - 1) : res.get(j - 1) + res.get(j);
                cache.add(num);
            }
            res.clear();
            res.addAll(cache);
            cache.clear();
        }
        return res;
    }

    public static List<Integer> getRow2(int rowIndex) {
        if (rowIndex < 0) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>(rowIndex + 1);
        res.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j > 0; j--) {
                res.set(j, res.get(j) + res.get(j - 1));
            }
            res.add(1);
        }
        return res;
    }

    public static void main(String[] args) {
        List<Integer> row = getRow2(3);
        System.out.println(row);
    }
}
